package com.killer.hash;

/**
 * 散列表
 * @param <K>
 * @param <V>
 */
public class MyHashMap<K,V> implements MyMap<K,V> {

    /**
     * 底层存储的数组(每个数组里面存的都是Node)
     */
    private NodeList<K,V>[] nodeList;

    /**
     * 元素个数
     */
    private int size=0;

    /**
     * nodeList[]非空的个数
     */
    private int occupy=0;

    /**
     * 扩容阈值 当occupy 达到 nodeList*threshold时,数组扩容,以避免太多hash冲突
     */
    private float threshold=0.75f;

    public MyHashMap(){
        //默认容量是4
        nodeList = new NodeList[4];
    }

    public void put(K k, V v) {
        //计算该key对应的数组下表
        int index = calKeyIndex(k,nodeList.length);
        //获取对应的Node
        NodeList<K, V> node = nodeList[index];
        if (node == null) {
            //如果node为空,则代表会新占用一个数组下表
            occupy++;
            node=new NodeList<K, V>();
            nodeList[index]=node;
        }
        //往该NodeList添加node
        boolean isAdd = node.add(k, v);
        if (isAdd) {
            size++;
        }
        //判断是否需要扩容
        if (occupy >= threshold * nodeList.length) {
            resize();
        }
    }

    private void resize() {
        //创建一个数组,容量是原来的2倍
        NodeList<K, V>[] newList = new NodeList[nodeList.length * 2];
        //occupy先重置
        occupy=0;
        //遍历该数组
        for(int i=0;i<nodeList.length;i++) {
            NodeList<K, V> oldNode = nodeList[i];
            if (oldNode == null||oldNode.head==null) {
                //如果原来该下标就没数据则跳过
                continue;
            }
            Node<K,V> dataNode=oldNode.head;
            //这个遍历
            while (dataNode != null) {
                //重新计算下标值
                int newIndex = calKeyIndex(dataNode.key, newList.length);
                //获取对应的新node
                NodeList<K, V> newNode = newList[newIndex];
                if (newNode == null) {
                    occupy++;
                    newNode=new NodeList<K, V>();
                    newList[newIndex]=newNode;
                }
                newNode.add(dataNode.key, dataNode.value);
                dataNode=dataNode.next;
            }

        }

        nodeList=newList;
    }

    public V get(K k) {
        //计算该key对应的数组下表
        int index = calKeyIndex(k,nodeList.length);
        //找到对应的NodeList
        NodeList<K, V> node = nodeList[index];
        //如果该下表下没有元素,直接返回空
        if (node == null) {
            return null;
        }
        Node<K, V> dataNode = node.get(k);
        return dataNode==null?null:dataNode.value;
    }

    public int size() {
        return size;
    }

    /**
     * 计算该key应该存放到的数组下标
     * @return
     */
    private int calKeyIndex(K k,int length){
       return Math.abs(k.hashCode())%length;
    }

    private class NodeList<K,V>{
        /**
         * 头节点
         */
        Node<K,V> head;

        /**
         * 插入节点
         * @param k
         * @param v
         * @return 是否是新增 true:新增 false:修改
         */
        public boolean add(K k,V v){
            //判断头结点是否为空
            if (head == null) {
                //直接赋值给头结点
                head = new Node<K, V>(k, v);
                return true;
            }
            //判断头结点的key是否等于该key
            if (head.key.equals(k)) {
                head.value=v;
                return false;
            }
            Node<K,V> tmp=head;
            //一直遍历
            while (tmp.next != null) {
                //不等就遍历下一个元素
                tmp=tmp.next;
                //判断key是否相等
                if (tmp.key.equals(k)) {
                    //如果key相等,则覆盖value的值
                    tmp.value=v;
                    return false;
                }
            }
            //都没有找到匹配,则直接挂载到最后一个节点
            tmp.next=new Node<K, V>(k, v);
            return true;
        }

        /**
         * 根据key获取对应节点
         * @param k
         * @return
         */
        public Node<K, V> get(K k) {
            //如果头结点为空,直接返回空即可
            if (head == null) {
                return null;
            }
            Node<K,V> tmp=head;
            //逐个遍历
            while (tmp!= null) {
                //对比key是否相等
                if (tmp.key.equals(k)) {
                    return tmp;
                }
                tmp=tmp.next;
            }
            //都没有匹配的则返回空
            return null;
        }

    }

    private class Node<K,V>{

        /**
         * 键
         */
        K key;

        /**
         * 数据域
         */
        V value;

        /**
         * 指针域
         */
        Node<K,V> next;


        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}
